G. caudovittatus có chiều dài cơ thể tối đa được biết đến là 20 cm[3]. Cơ thể thuôn dài, đầu (nhìn nghiên) tròn[4]. Chúng là một loài dị hình giới tính rõ rệt.

Cá cái tổng thể có màu nâu xám nhạt hoặc màu be (sẫm màu hơn ở lưng và thân trên). Trên trán có một vệt đốm đen và có thể lan rộng xuống mắt. Vùng thân giữa vây lưng sau và cuống đuôi trên có vệt đen. Hai thùy đuôi trên và dưới của chúng có viền đen. Vây lưng và vây hậu môn màu trắng, có viền xanh lam óng[4].

Cá đực có hoa văn nổi bật hơn cá cái: thân có màu be (hơi phớt màu xanh lam nhạt) với các vệt sọc đen ở hai bên thân (và trên cả đỉnh đầu) như hoa văn của ngựa vằn. Cuống đuôi và phần gai vây lưng có màu vàng, trên vây lưng còn có một vệt đen lớn. Hai thùy đuôi của cá đực rất dài[4].

Số gai vây lưng: 15; Số tia vây ở vây lưng: 15–17; Số gai vây hậu môn: 3; Số tia vây ở vây hậu môn: 17–19[3].